#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef struct BinaryTreeNode BTNode;

typedef BTNode* STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}Stack;

//初始化
void STInit(Stack* pst);
//销毁
void STDestroy(Stack* pst);
//插入
void STPush(Stack* pst, STDataType x);
//删除
void STPop(Stack* pst);
//获取栈顶数据
STDataType STTop(Stack* pst);
//判断是否为空
bool STEmpty(Stack* pst);
//剩余数据个数
int STSize(Stack* pst);

void CheckCapacity(Stack* pst)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = (pst->capacity == 0) ? 4 : (pst->capacity * 2);
		STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		pst->data = tmp;
		pst->capacity = newcapacity;
	}
}

//初始化
void STInit(Stack* pst)
{
	assert(pst);
	pst->data = NULL;
	//top指向栈顶数据的下一个位置
	pst->top = 0;
	pst->capacity = 0;
}

//销毁
void STDestroy(Stack* pst)
{
	assert(pst);
	free(pst->data);
	pst->capacity = 0;
	pst->top = 0;
}

//插入
void STPush(Stack* pst, STDataType x)
{
	assert(pst);
	CheckCapacity(pst);
	pst->data[pst->top++] = x;
}

//删除
void STPop(Stack* pst)
{
	assert(pst);
	if(pst->top > 0)
	pst->top--;
}

//获取栈顶数据
STDataType STTop(Stack* pst)
{
	assert(pst);
	assert(!STEmpty(pst));

	return pst->data[pst->top - 1];
}

//判断是否为空
bool STEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;
}

//剩余数据个数
int STSize(Stack* pst)
{
	assert(pst);
	return pst->top;
}




typedef int BTDataType;

typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if(newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }

    newnode->_data = x;
    newnode->_left = NULL;
    newnode->_right = NULL;

    return newnode;
}

BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
 
    node1->_left = node2;
    node1->_right = node4;
    node2->_left = node3;
    node4->_left = node5;
    node4->_right = node6;
    return node1;
}

//先序遍历的递归算法
void PreOrder1(BTNode* b)
{
    if(b == NULL)
    return;

    //访问根结点
    printf("%d ", b->_data);
    //访问左子树
    PreOrder1(b->_left);
    //访问右子树
    PreOrder1(b->_right);
}

//先序遍历的非递归算法1
void PreOrder2(BTNode* b)
{
    Stack st;
    STInit(&st);
    BTNode* p = b;
    if(b != NULL)
    {
        STPush(&st, p);//根结点入栈
        while(!STEmpty(&st))
        {
            p = STTop(&st);
            printf("%d ", p->_data);
            STPop(&st);

            if(p->_right != NULL)
            STPush(&st, p->_right);
            if(p->_left != NULL)
            STPush(&st, p->_left);
        }
    }
    STDestroy(&st);
}

//先序遍历的非递归算法2
void PreOrder3(BTNode* b)
{
    Stack st;
    STInit(&st);
    BTNode* p = b;
    while(!STEmpty(&st) || p != NULL)
    {
        //访问根结点并依次访问左孩子
        while(p != NULL)
        {
            STPush(&st, p);
            printf("%d ", p->_data);
            p = p->_left;
        }
        //退回上一层，找右孩子
        if(!STEmpty(&st))
        {
            p = STTop(&st);
            STPop(&st);
            p = p->_right;
        }
    }
    
    STDestroy(&st);
}

//中序遍历的递归算法
void MidOrder1(BTNode* b)
{
    if(b == NULL)
    return;

    //访问左子树
    MidOrder1(b->_left);
    //访问根结点
    printf("%d ", b->_data);
    //访问右子树
    MidOrder1(b->_right);
}

//中序遍历的非递归算法
void MidOrder2(BTNode* b)
{
    Stack st;
    STInit(&st);
    BTNode* p = b;
    while(!STEmpty(&st) || p != NULL)
    {
        //将p及左孩子依次入栈
        while(p != NULL)
        {
            STPush(&st, p);
            p = p->_left;
        }
        //退回上一层并访问根结点，找右孩子
        if(!STEmpty(&st))
        {
            p = STTop(&st);
            STPop(&st);
            printf("%d ", p->_data);
            p = p->_right;
        }
    }
    STDestroy(&st);
}

//后序遍历的递归算法
void AftOrder1(BTNode* b)
{
    if(b == NULL)
    return;

    //访问左子树
    AftOrder1(b->_left);
    //访问右子树
    AftOrder1(b->_right);
    //访问根结点
    printf("%d ", b->_data);
}

//后序遍历的非递归算法
void AftOrder2(BTNode* b)
{
    Stack st;
    STInit(&st);
    BTNode* p = b;
    BTNode* asked = NULL;//指向刚刚访问过的结点
    bool flag = true;//为真表示正在处理栈顶结点
    do
    {
        //p及左孩子依次进栈
        while(p != NULL)
        {
            STPush(&st, p);
            p = p->_left;
        }
        asked = NULL;
        flag = true;

        while(!STEmpty(&st) && flag)
        {
            p = STTop(&st);
            if(p->_right == asked)//右孩子刚被访问过或者为空
            {
                printf("%d ", p->_data);
                STPop(&st);
                asked = p;
            }
            else
            {
                p = p->_right;
                flag = false;
            }
        }
    } while (!STEmpty(&st));
    
    STDestroy(&st);
}


int main()
{
    BTNode* bt = CreatBinaryTree();
    PreOrder3(bt);
    printf("\n");
    MidOrder2(bt);
    printf("\n");
    AftOrder2(bt);
    printf("\n");
    return 0;
}